package tree;

public class threadedBinaryTreeDemo {
	public static void main(String[] args) {
		threadedBinaryTree threadedBinaryTree = new threadedBinaryTree();

		HeroNode2 node1 = new HeroNode2(1, "qqq");
		HeroNode2 node2 = new HeroNode2(2, "www");
		HeroNode2 node3 = new HeroNode2(3, "eee");
		HeroNode2 node4 = new HeroNode2(4, "rrr");
		HeroNode2 node5 = new HeroNode2(5, "ttt");
		HeroNode2 node6 = new HeroNode2(6, "yyy");

		//手动创建二叉树
		node1.setLeft(node2);
		node1.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);

		//测试线索化
		threadedBinaryTree.setRoot(node1);

//        threadedBinaryTree.threadedPreNode(node1);//1.2.4.5.3.6

//        threadedBinaryTree.threadedNodes(node1);

		threadedBinaryTree.threadedPostNode(node1);//4.5.2.6.3.1

		//10号节点
//        HeroNode2 node5Left = node5.getLeft();
//        System.out.println(node5Left);
//        HeroNode2 node5Right = node5.getRight();
//        System.out.println(node5Right);

		//遍历

//        threadedBinaryTree.threadedPre();

//        threadedBinaryTree.threadedList();

		threadedBinaryTree.threadedPost(node1);
	}

}

//定义一个二叉树，实现了线索化的
class threadedBinaryTree {
	private HeroNode2 root;

	//为了实现线索化，需要创建要给指向当前节点的前驱的指针
	//递归进行线索化是，pre总是保留前一个节点
	private HeroNode2 pre = null;

	public void setRoot(HeroNode2 root) {
		this.root = root;
	}

	public HeroNode2 getRoot() {
		return root;
	}

	//  前序遍历
	public void threadedPre() {
		HeroNode2 node = root;
		while (node != null) {
			System.out.println(node);
			while (node.getLeftType() == 0) {
				node = node.getLeft();
				System.out.println(node);
			}
			while (node.getRightType() == 1) {
				node = node.getRight();
				System.out.println(node);
			}
			node = node.getRight();
		}
	}

	//遍历线索化二叉树，不能使用原先的遍历方法，会死循环
	public void threadedList() {
		//定义一个变量，存储当前遍历的节点
		HeroNode2 node = root;
		while (node != null) {
			//循环找到 leftType = 1 的节点
			while (node.getLeftType() == 0) {
				node = node.getLeft();
			}

			//打印当前节点
			System.out.println(node);
			//如果当前节点的右指针指向后继节点，就一直输出
			while (node.getRightType() == 1) {
				node = node.getRight();
				System.out.println(node);
			}
			//替换遍历的节点
			node = node.getRight();

		}
	}

	//  后序遍历
	public void threadedPost(HeroNode2 n) {
		HeroNode2 node = n.getLeft();
		if (node != null) {
			while (node.getLeft() != null && node.getLeftType() == 0) {
				node = node.getLeft();
			}
			System.out.println(node);
			while (node.getRightType() == 1) {
				node = node.getRight();
				System.out.println(node);
			}
		}
		if (n.getRight() != null && n.getRightType() == 0) {
			threadedPost(n.getRight());
		}
	}

	//对二叉树 前序 线索化
	public void threadedPreNode(HeroNode2 node) {
		if (node == null) {
			return;
		}

		//2. 线索化当前节点
		//2.1 处理当前节点的前驱节点
		if (node.getLeft() == null) {
			//让当前节点，左指针指向前驱节点
			node.setLeft(pre);
			//修改当前节点左指针的类型
			node.setLeftType(1);
		}
		//2.2 处理后继节点
		if (pre != null && pre.getRight() == null) {
			pre.setRight(node);
			pre.setRightType(1);
		}
		pre = node;

		if (node.getLeftType() == 0) {
			threadedPreNode(node.getLeft());
		}
		if (node.getRightType() == 0) {
			threadedPreNode(node.getRight());
		}
	}


	//对二叉树 中序 线索化
	//node 为需要线索话的节点
	public void threadedNodes(HeroNode2 node) {
		if (node == null) {
			return;
		}

		//1. 先线索化左子树
		threadedNodes(node.getLeft());

		//2. 线索化当前节点
		//2.1 处理当前节点的前驱节点
		if (node.getLeft() == null) {
			//让当前节点，左指针指向前驱节点
			node.setLeft(pre);
			//修改当前节点左指针的类型
			node.setLeftType(1);
		}
		//2.2 处理后继节点
		if (pre != null && pre.getRight() == null) {
			pre.setRight(node);
			pre.setRightType(1);
		}
		pre = node;

		//3. 线索化右子树
		threadedNodes(node.getRight());

	}

	//对二叉树 后序 线索化
	public void threadedPostNode(HeroNode2 node) {
		if (node == null) {
			return;
		}
		if (node.getLeftType() == 0) {
			threadedPostNode(node.getLeft());
		}
		if (node.getRightType() == 0) {
			threadedPostNode(node.getRight());
		}

		if (node.getLeft() == null) {
			node.setLeft(pre);
			node.setLeftType(1);
		}
		if (pre != null && pre.getRight() == null) {
			pre.setRight(node);
			pre.setRightType(1);
		}
		pre = node;
	}

	//前序遍历(调用 HeroNode 中的方法)
	public void preOrder() {
		if (this.root != null) {
			this.root.preOrder();
		} else {
			System.out.println("为空");
		}
	}

	//前序遍历(调用 HeroNode 中的方法)
	public void infixOrder() {
		if (this.root != null) {
			this.root.infixOrder();
		} else {
			System.out.println("为空");
		}
	}

	//前序遍历(调用 HeroNode 中的方法)
	public void postOrder() {
		if (this.root != null) {
			this.root.postOrder();
		} else {
			System.out.println("为空");
		}
	}

	//前序查找
	public void preOrderSearch(int no) {
		if (root != null) {
			System.out.println(root.preOrderSearch(no));
		} else {
			System.out.println("不存在");
		}
	}

	//中序查找
	public void infixOrderSearch(int no) {
		if (root != null) {
			System.out.println(root.infixOrderSearch(no));
		} else {
			System.out.println("不存在");
		}
	}

	//后序查找
	public void postOrderSearch(int no) {
		if (root != null) {
			System.out.println(root.postOrderSearch(no));
		} else {
			System.out.println("不存在");
		}
	}

	//删除节点
	public void deleteNode(int no) {
		if (root != null) {
			//如果root 只有一个节点，判断root 是不是要删的
			if (root.getNo() == no) {
				root = null;
			} else {
				root.deleteNode(no);
			}
		} else {
			System.out.println("为空");
		}
	}

}

//创建 HeroNode 节点
class HeroNode2 {
	private int no;
	private String name;
	private HeroNode2 left;
	private HeroNode2 right;

	//如果 leftType = 0 表示指向左子树，如果leftType = 1 表示指向钱去
	//rightType = 0 -> 右子树,rightType = 1 -> 后继
	private int leftType = 0;
	private int rightType = 0;

	public HeroNode2(int no, String name) {
		this.no = no;
		this.name = name;
	}

	public int getNo() {
		return no;
	}

	public void setNo(int no) {
		this.no = no;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode2 getLeft() {
		return left;
	}

	public void setLeft(HeroNode2 left) {
		this.left = left;
	}

	public HeroNode2 getRight() {
		return right;
	}

	public void setRight(HeroNode2 right) {
		this.right = right;
	}

	public int getLeftType() {
		return leftType;
	}

	public void setLeftType(int leftType) {
		this.leftType = leftType;
	}

	public int getRightType() {
		return rightType;
	}

	public void setRightType(int rightType) {
		this.rightType = rightType;
	}

	@Override
	public String toString() {
		return "HeroNode{" +
				"no=" + no +
				", name='" + name + '\'' +
				'}';
	}

	//前序遍历的方法
	public void preOrder() {
		//1.先输出父节点
		System.out.println(this);
		//2.递归向左子树前序遍历
		if (this.left != null) {
			this.left.preOrder();
		}
		//3.递归向右子树前序遍历
		if (this.right != null) {
			this.right.preOrder();
		}
	}

	//中序
	public void infixOrder() {
		//1.递归向左子树中序遍历
		if (this.left != null) {
			this.left.infixOrder();
		}
		//2.输出父节点
		System.out.println(this);
		//3.递归向右子树中序遍历
		if (this.right != null) {
			this.right.infixOrder();
		}
	}

	//后序
	public void postOrder() {
		//1.递归向左子树中序遍历
		if (this.left != null) {
			this.left.postOrder();
		}
		//2.递归向右子树中序遍历
		if (this.right != null) {
			this.right.postOrder();
		}
		//3.输出父节点
		System.out.println(this);
	}

	//前序遍历查找
	public HeroNode2 preOrderSearch(int no) {
		//比较当前节点是不是
		if (this.no == no) {
			return this;
		}

		HeroNode2 resultNode = null;
		if (this.left != null) {
			resultNode = this.left.preOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在左子树上找到了
			return resultNode;
		}
		if (this.right != null) {
			resultNode = this.right.preOrderSearch(no);
		}

		return resultNode;
	}

	//中序遍历查找
	public HeroNode2 infixOrderSearch(int no) {

		HeroNode2 resultNode = null;
		if (this.left != null) {
			resultNode = this.left.infixOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在左子树上找到了
			return resultNode;
		}

		//比较当前节点是不是
		if (this.no == no) {
			return this;
		}

		if (this.right != null) {
			resultNode = this.right.infixOrderSearch(no);
		}

		return resultNode;
	}

	//后序遍历查找
	public HeroNode2 postOrderSearch(int no) {
		HeroNode2 resultNode = null;
		if (this.left != null) {
			resultNode = this.left.postOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在左子树上找到了
			return resultNode;
		}
		if (this.right != null) {
			resultNode = this.right.postOrderSearch(no);
		}
		if (resultNode != null) {
			//如果成立在右子树上找到了
			return resultNode;
		}
		//比较当前节点是不是
		if (this.no == no) {
			return this;
		}
		return resultNode;
	}


	//递归删除节点
	public void deleteNode(int no) {
		//先判断左子节点是否是要删除的
		if (this.left != null && this.left.no == no) {
			this.left = null;
			return;
		}
		//先判断右子节点是否是要删除的
		if (this.right != null && this.right.no == no) {
			this.right = null;
			return;
		}

		//左右都不是，向左子树递归
		if (this.left != null) {
			this.left.deleteNode(no);
		}

		//左右都不是，向右子树递归
		if (this.right != null) {
			this.right.deleteNode(no);
		}
	}

}
